package SearchBinaryTree;

public class SearchBinaryTreeNode<T> {
    T data;
    public SearchBinaryTreeNode<T> leftChild;
    public SearchBinaryTreeNode<T> rightChild;
    
    public SearchBinaryTreeNode(){
        this.data=null;
        this.leftChild=this.rightChild=null;
    }
    
    public SearchBinaryTreeNode(T da){
        this.data=da;
        this.leftChild=this.rightChild=null;
    }
    
    public SearchBinaryTreeNode(T da,SearchBinaryTreeNode<T> left,SearchBinaryTreeNode<T>right){
        this.data=da;
        this.leftChild=left;
        this.rightChild=right;
    }
    
    public boolean isLeaf(){
        if(this.leftChild==null&&this.rightChild==null){
            return true;
        }
        return false;
    }
}

public class SearchBinaryTree<T> {
    SearchBinaryTreeNode<T> root;

    /*
     * 创造一颗二叉树
     */
    public void createTree(SearchBinaryTreeNode<T> node, T data) {
        if (root == null) {
            root = new SearchBinaryTreeNode<T>();
        } else {
            if (Math.random() > 0.5) {                   //采用随机方式创建二叉树
                if (node.leftChild == null) {
                    node.leftChild = new SearchBinaryTreeNode<T>(data);
                } else {
                    createTree(node.leftChild, data);
                }
            } else {
                if (node.rightChild == null) {
                    node.rightChild = new SearchBinaryTreeNode<T>(data);
                } else {
                    createTree(node.rightChild, data);
                }
            }
        }
    }
    
    /*
     * 在二查搜索树中进行搜索
     */
    public SearchBinaryTreeNode<T> search(SearchBinaryTreeNode<T> root,T value){
        SearchBinaryTreeNode<T> current = root;
        while((root != null)&&( current.getData() != value)){
            //需要注意的是java中泛型无法比较大小，在实际的使用时我们可以使用常见的数据类型来替代这个泛型，这样就不会出错了
            current=( value < current.getData() ? 
               search(current.leftChild,value) : search(current.rightChild,value));
        }
        return current;
    }

    public SearchBinaryTreeNode<T> insertNode( T value){
        SearchBinaryTreeNode<T> p=root,pre=null;
        while(p!=null){
            pre=p;
            //需要注意的是java中泛型无法比较大小，在实际的使用时我们可以使用常见的数据类型来替代这个泛型，这样就不会出错了
            if(p.getData() < value){
                p=p.rightChild;
            }else{
                p=p.leftChild;
            }
        }
        if(root==null){
            root=new SearchBinaryTreeNode<T>(value);
        }else if(pre.getData()<value){
            pre.rightChild=new SearchBinaryTreeNode<T>(value);
        }else{
            pre.leftChild=new SearchBinaryTreeNode<T>(value);
        }
    }

    /*
     * 合并删除
     */
    public void deleteByMerging(SearchBinaryTreeNode<T> node){
        SearchBinaryTreeNode<T> temp=node;
        if(node!=null){
            //若被删除节点没有右子树,用其左子树的根节点来代替被删除节点
            if(node.rightChild!=null){
                node=node.leftChild;
            }else if(node.leftChild==null){
                //若被删节点没有左子树，用其有字数的最左端的节点代替被删除的节点
                node=node.rightChild;
            }else{
                //如果被删节点左右子树均存在
                temp=node.leftChild;
                while(temp.rightChild!=null){
                    temp=temp.rightChild;     //一直查找到左子树的右节点
                }
                
                //将查找到的节点的右指针赋值为被删除节点的右子树的根
                temp.rightChild=node.rightChild;
                temp=node;
                node=node.leftChild;
            }
            temp=null;
        }
    }

    /*
     * 复制删除
     */
    public void deleteByCoping(SearchBinaryTreeNode<T> node){
        SearchBinaryTreeNode<T> pre=null;
        SearchBinaryTreeNode<T> temp=node;
        //如果被删节点没有右子树，用其左子树的根节点来代替被删除节点
        if(node.rightChild==null){
            node=node.leftChild;
        }else if(node.leftChild==null){
            node=node.rightChild;
        }else{
            //如果被删节点的左右子树都存在
            temp=node.leftChild;
            pre=node;
            while(temp.rightChild!=null){
                pre=temp;
                temp=temp.rightChild;      //遍历查找到左子树的最右端的节点
            }
            node.data=temp.data;           //进行赋值操作
            if(pre==node){
                pre.leftChild=node.leftChild;
            }else{
                pre.rightChild=node.rightChild;
            }
        }
        temp=null;
    }

}

